package com.tgy.algorithm.base;

import java.util.Arrays;

public class _基数排序_01 {

    public static void radixSort(int[] nums) {

        // 11,32,21,80,58,101
        // 1,3,1,0,0,0,0,0,1
        // 1,4,5,5,5,5,5,5,6
        int max = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (max < nums[i]) {
                max = nums[i];
            }
        }

        int maxBits = getValBitCount(max);
        int[] numbits = new int[10];

        for (int i = 1; i <= maxBits; i++) {

            for (int j = 0; j < numbits.length; j++) {
                numbits[j] = 0;
            }

            for (int num  : nums) {
                int valBit = getValBit(num, i);
                numbits[valBit]++;
            }

            for (int j = 1; j < numbits.length; j++) {
                numbits[j] = numbits[j - 1] + numbits[j];
            }

            int[] tmpNums = new int[nums.length];

            for (int j = nums.length - 1; j >= 0; j--) {
               int bitVal = getValBit(nums[j], i);
               tmpNums[--numbits[bitVal]] = nums[j];
            }

            for (int j = 0; j < nums.length; j++) {
                nums[j] = tmpNums[j];
            }
        }

    }

    public static int getValBit(int val, int bit) {
        int ret = 0;
        int index = 0;
        while (val > 0) {
            ret = val % 10;
            index++;
            if (index == bit) {
                return ret;
            }
            val = val / 10;
        }
        return 0;
    }

    public static int getValBitCount(int val) {

        int count = 0;
        while (val > 0) {
            val = val / 10;
            count++;
        }
        return count;
    }

    public static void main(String[] args) {

//        int valBit = getValBit(123, 4);
//        System.out.println(valBit);
//        int valBitCount = getValBitCount(1222229);
//        System.out.println(valBitCount);
        int[] nums = {11, 32, 21, 80, 58, 101};
        radixSort(nums);
        System.out.println(Arrays.toString(nums));
    }
}
